CBC Casper: Safety Oracles fault tolerance
Threshold $ T(\sigma)
とは、現在の状態$ \sigmaにおいて、将来どんなことが起こってもfaultの数が$ t未満であれば、その将来の状態を$ \sigma'について$ W(\mathrm{Agreeing}(p,\sigma')) > W(\mathrm{Disagreeing}(p,\sigma'))が成り立つような、あるバリデータ集合の重みの総和の閾値
Clique Oracle であれば、maximum weighted clique の重みが$ T(\sigma)より大きければいい
fault tolerance が小さいほど Threshold が大きい
Clique Oracle threshold
etherem/cbc-casper
fault_tolerance = 2 * clique_weight - self.validator_set.weight()
とあるが、これは、おそらく
$ t = 2T(\sigma) - (W(\mathcal{V}) - F(\sigma)) … (i)
を意味している（$ t=2T(\sigma) - W(\mathcal{V})じゃなさそう）
将来のある状態$ \sigma'において、クリークから$ t-1個の equivocating validators が現れるという最悪な結果が起きても、それら equivocating validators を検知できるのでバリデータセットから省くことができる。よって上の式(i)が成り立つ。
例えば$ W(\mathcal{V}) = 100, F(\sigma) = 10, T(\sigma) = 60とすると$ t = 30
これから29個のクリーク内部のバリデータがequivocateしても、「サイズ31のクリーク」と「30個のクリークに属していないバリデータ」と変化し、31(agree) > 30(disagree) となり結果が覆らない
(i)を式変形すると、
$ T(\sigma) = \frac{W(\mathcal{V}) - F(\sigma)}{2} + \frac{t}{2} （①）
現在のなかむさんペーパーの Clique Oracle threshold
$ T(\sigma) = \frac{W(\mathcal{V})}{2} + t - F(\sigma)
$ = \frac{W(\mathcal{V})-F(\sigma)}{2} + \frac{t-F(\sigma)}{2} + \frac{t}{2}（②）
$ t - F(\sigma) \ge 0より ①<=②
以前のなかむさんペーパーの Clique Oracle threshold
$ T(\sigma) = \frac{W(\mathcal{V})}{2} + \frac{t}{2} - F(\sigma)
$ = \frac{W(\mathcal{V}) - F(\sigma)}{2} + \frac{t}{2} - \frac{F(\sigma)}{2}（③）
$ F(\sigma) \ge 0より③<=①
$ T(\sigma)が小さいほどファイナリティ検知が早い
③<=①<=②
③が正しいなら①よりも③を採用すべき
（ただし③は成り立たないらしく論文がreviseされた）
②より①のほうがいい
Simple Finality Detector (Inspector) threshold
$ T(\sigma) = \frac{W(\mathcal{V}) - F(\sigma)}{2} + t（④）
$ t = T(\sigma) - \frac{W(\mathcal{V})-F(\sigma)}{2}
①<=②<=④
Clique Oracle より広い範囲のファイナリティを検知できるが、Thresholdが大きい（fault tolerance が小さい）
$ t_{\mathrm{Clique}} = 2t_{\mathrm{Simple}}が成り立つ
Clique Oracle の fault tolerance は、Simple Finality Detector の fault tolerance の2倍
例
https://gyazo.com/f10641dcf34ae64353666fb32b41a63f
Clique Oracle: $ t = 2T(\sigma) - (W(\mathcal{V}) - F(\sigma)) = 2\cdot 4 - 4 = 4
Simple Finality Detector: $ t = T(\sigma) - \frac{W(\mathcal{V})-F(\sigma)}{2} = 4 - \frac{4}{2} = 2
厳密には、Clique Oracle で検知できるが、Simple Finality Detector だと検知できないファイナリティは存在する
「$ tが事前に決めておいた$ t'を超えた」ときに、「あるプロパティがfinalizeされた」とすると、$ t'=3のとき、Clique Oracle だと finalize されるが、Simple Finality Detector だと finalize されない
つまり、Clique Oracle よりファイナリティ検知の幅は大きいが攻撃に弱い
Improved Finality Detector (Inspector) threshold
$ q \ge \frac{n}{2} + \frac{t}{2(1-2^{-k})}
$ T(\sigma) = \frac{W(\mathcal{V}) - F(\sigma)}{2} + \frac{t}{2(1-2^{-k})}（⑤）
$ k=1: \frac{W(\mathcal{V}) - F(\sigma)}{2} + t
$ k=2: \frac{W(\mathcal{V}) - F(\sigma)}{2} + \frac{2t}{3}
$ k=3: \frac{W(\mathcal{V}) - F(\sigma)}{2} + \frac{4t}{7}
$ t = (1-2^{-k})(2T(\sigma) - (W(\mathcal{V})-F(\sigma)))
①<=③<=④
Simple Finality Detector より広い範囲のファイナリティを検知できる
レイヤーを重ねるとClique OracleのThreshold, fault toleranceに近づく
Clique Oracleより広い範囲のファイナリティを検知できるが、Simple Finality Detector同様、Thresholdが大きい（fault tolerance が小さい）
$ t_{\mathrm{Clique}} \ge t_{\mathrm{Improved}} \ge t_{\mathrm{Simple}}
$ t_{\mathrm{Clique}} = 2t_{\mathrm{Simple}}
例
https://gyazo.com/df50de9e0ce545b1e3ea2550cb7ea471
Clique Oracle: $ t = 2\cdot 4 - 4 = 4
Simple Finality Detector: $ t = 4 - \frac{4}{2} = 2
Improved Finality Detector: $ t = (1-\frac{1}{4})(8 - 4) = \frac{3}{4} \cdot 4 = 3
Simple Finality Detector同様、厳密にはClique Oracleに検知できてImproved Finality Detectorだと検知できないファイナリティがある
Adversary Oracle with Priority Queue (by minaminao) fault tolerance
Threshold (T)という概念はない
nrryuya.icon > といいつつ、Adversary oracle単体でのplausible livenessを議論するには、必要なhonest validator数のlower boundが欲しい
nrryuya.icon > そもそもどういうDAGの時にfinality検知できるんだっけという議論をする上でも欲しい
fault toleranceが大きい
$ t_{\mathrm{Clique}} \ge t_{\mathrm{Improved}} \ge t_{\mathrm{Simple}}
https://gyazo.com/f10641dcf34ae64353666fb32b41a63f
Clique Oracle: $ t=4
Simple Finality Detector: $ t = 2
Improved Finality Detector: $ t=2
Adversary Oracle : $ t = 4
計算量が小さい
Clique Oracle: exponential
Simple Finality Detector: $ O(V^2 + J)
Improved Finality Detector: $ O(VJ)
Adversary Oracle : $ O(V^2 + J)
Inspectorよりも広い範囲のファイナリティを検知できる
Inspector がレイヤーを重ねなくちゃいけないのは、fault tolerance が大きくしたいから
その点でこのAdversary Oracleはその問題を解決している
この Adversary Oracle は、
Simple Finality Detector と同じ計算量で、
fault tolerance が大きいことにより Improved Finality Detector よりも広い範囲のファイナリティを検知できる
※未証明（もし正しければとても優秀な気がする）